#include <windows.h>
#include "stdio.h"
#include "assert.h"
#include "lzocompress.h"

int LzoDecompress (const void *in , void *out)
{
    unsigned char *op;
    unsigned char *ip;
    unsigned long t;
    unsigned char *m_pos;

    op = (unsigned char *) out;
    ip = (unsigned char *) in;

    if (*ip > 17) {
		t = *ip++ - 17;
		if (t < 4)
			goto match_next;
		do *op++ = *ip++; while (--t > 0);
		goto first_literal_run;
    }

    for(;;) {
		t = *ip++;
		if (t >= 16) goto match;
		if (t == 0) {
			while (*ip == 0) {
				t += 255;
				ip++;
				}
			t += 15 + *ip++;
			}

	* (unsigned long *) op = * ( unsigned long *) ip;
	op += 4; ip += 4;
	if (--t > 0)
	{
	    if (t >= 4)
	    {
		do {
		    * (unsigned long * ) op = * ( unsigned long * ) ip;
		    op += 4; ip += 4; t -= 4;
		} while (t >= 4);
		if (t > 0) do *op++ = *ip++; while (--t > 0);
	    }
	    else do *op++ = *ip++; while (--t > 0);
	}

first_literal_run:

	t = *ip++;
	if (t >= 16)
	    goto match;

	m_pos = op - 0x0801;
	m_pos -= t >> 2;
	m_pos -= *ip++ << 2;

	*op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos;

	goto match_done;

	for(;;)
	{
match:
	    if (t >= 64)
	    {

		m_pos = op - 1;
		m_pos -= (t >> 2) & 7;
		m_pos -= *ip++ << 3;
		t = (t >> 5) - 1;

		goto copy_match;

	    }
	    else if (t >= 32)
	    {
			t &= 31;
			if (t == 0)	{
				while (*ip == 0) {
					t += 255;
					ip++;
					}
		    t += 31 + *ip++;
			}

			m_pos = op - 1;
			m_pos -= (* ( unsigned short * ) ip) >> 2;
			ip += 2;
		}
	    else if (t >= 16) {
			m_pos = op;
			m_pos -= (t & 8) << 11;
			t &= 7;
			if (t == 0) {
				while (*ip == 0) {
					t += 255;
					ip++;
					}
				t += 7 + *ip++;
				}
			m_pos -= (* ( unsigned short *) ip) >> 2;
			ip += 2;
			if (m_pos == op)
				goto eof_found;
			m_pos -= 0x4000;
			}
	    else {
			m_pos = op - 1;
			m_pos -= t >> 2;
			m_pos -= *ip++ << 2;
			*op++ = *m_pos++; *op++ = *m_pos;
			goto match_done;
	    }

		if (t >= 6 && (op - m_pos) >= 4) {
			* (unsigned long *) op = * ( unsigned long *) m_pos;
			op += 4; m_pos += 4; t -= 2;
			do {
				* (unsigned long *) op = * ( unsigned long *) m_pos;
				op += 4; m_pos += 4; t -= 4;
			} while (t >= 4);
			if (t > 0) do *op++ = *m_pos++; while (--t > 0);
	    }
	    else {
copy_match:
		*op++ = *m_pos++; *op++ = *m_pos++;
		do *op++ = *m_pos++; while (--t > 0);
	    }

match_done:

	    t = ip[-2] & 3;
	    if (t == 0)	break;

match_next:
	    do *op++ = *ip++; while (--t > 0);
	    t = *ip++;
	}
   }

eof_found:
//   if (ip != ip_end) return -1;
   return (op - (unsigned char*)out);
}

static unsigned long _do_compress ( unsigned char *in , unsigned long in_len,
				 unsigned char *out, unsigned long *out_len)
{
	long wrkmem  [16384L] ;
	unsigned char *ip;
	unsigned char *op;
	unsigned char *  in_end = in + in_len;
	unsigned char *  ip_end = in + in_len - 13;
	unsigned char *ii;
	unsigned char **   dict = ( unsigned char ** ) wrkmem;

    op = out, ip = in ,  ii = ip;

    ip += 4;

    for (;;) {
		 unsigned char *m_pos;
		unsigned long m_off;
		unsigned long m_len;
		unsigned long dindex;

		dindex = ((0x21*(((((((unsigned long)(ip[3])<<6)^ip[2])<<5)^ip[1])<<5)^ip[0]))>>5) & 0x3fff;
		m_pos = dict [dindex];



		if  (((unsigned long)m_pos < (unsigned long)in)  || 
			(m_off = (unsigned long)((unsigned long)ip-(unsigned long)m_pos) ) <= 0 ||
			m_off > 0xbfff)  
			goto literal;

		if (m_off <= 0x0800  || m_pos[3] == ip[3])
			goto try_match;
		dindex  = ( dindex  & 0x7ff ) ^ 0x201f ;

		m_pos  =  dict [dindex] ;
		if ( (unsigned long)(m_pos)  < (unsigned long)(in)   ||
			(m_off = (unsigned long)( (int)((unsigned long)ip-(unsigned long)m_pos))) <= 0 ||
			m_off  >  0xbfff  )   
		    goto literal;
		if (m_off <= 0x0800  || m_pos[3] == ip[3])
			goto try_match;
		goto literal;

try_match:

		if (*( unsigned short*)m_pos == *( unsigned short*)ip && m_pos[2]==ip[2]) 
				goto match;

literal:
	 dict[dindex] = ip;
	 ++ip;
	 if (ip >= ip_end)
	    break;
	 continue;

match:
	 dict[dindex] =  ip;
	 if (ip - ii > 0) {
	    unsigned long t = ip - ii;

	    if (t <= 3) 
			op[-2] |= (unsigned char)t;
	    else if (t <= 18)
			*op++ = (unsigned char) ( t - 3 );
	    else {
			unsigned long tt = t - 18;
			*op++ = 0;
			while (tt > 255) {
				tt -= 255;
				*op++ = 0;
			}
			*op++ = (unsigned char)tt;
	    }
	    do *op++ = *ii++; while (--t > 0);
	}

	ip += 3;

	if (m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++ ||
	    m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++ ) {
	    --ip;
	    m_len = ip - ii;
	    
	    if (m_off <= 0x0800 ) {
			--m_off;
			*op++ = (unsigned char) ( ((m_len - 1) << 5) | ((m_off & 7) << 2) );
			*op++ = (unsigned char) ( m_off >> 3 );
	    }
	    else if (m_off <= 0x4000 ) {
			-- m_off;
			*op++ = (unsigned char) ( 32  | (m_len - 2) );
			goto m3_m4_offset;
	    }
	    else {
			m_off -= 0x4000;
			*op++ = (unsigned char) (16 | ((m_off & 0x4000) >> 11) | (m_len - 2) );
			goto m3_m4_offset;
	    }
	}
	else
	{
	    {
		 unsigned char *end = in_end;
		 unsigned char *m = m_pos + 9;
		while (ip < end && *m == *ip)
		    m++, ip++;
		m_len = (ip - ii);
	    }

	    if (m_off <= 0x4000 )  {
			--m_off;
			if (m_len <= 33)
				*op++ = (unsigned char) ( 32  | (m_len - 2) );
			else {
				m_len -= 33;
				*op++=32;
				goto m3_m4_len;
				}
	    }
	    else {
			m_off -= 0x4000;
			if (m_len <= 9 )
				*op++ = (unsigned char)(16|((m_off & 0x4000) >> 11) | (m_len - 2));
		else {
		    m_len -= 9;
		    *op++ = (unsigned char) ( 16  | ((m_off & 0x4000) >> 11) );
m3_m4_len:
		    while (m_len > 255) {
				m_len -= 255;
				*op++ = 0;
		    }
		    *op++ = (unsigned char)m_len;
			}
		}

m3_m4_offset:
	    *op++ = (unsigned char) ( (m_off & 63) << 2 );
	    *op++ = (unsigned char) ( m_off >> 6 );
	}

	ii = ip;
	if (ip >= ip_end)
	    break;
    }

    *out_len = op - out;
    return (unsigned long) (in_end - ii);
}

int LzoCompress (  const void *in , unsigned long  in_len,
			 void *out)
{
    unsigned char *op = (unsigned char *)out;
    unsigned long t,out_len;

    if (in_len <= 13)
		t = in_len;
    else {
		t = _do_compress ((unsigned char *)in,in_len,op,&out_len);
		op += out_len;
    }

    if (t > 0) {
	 unsigned char *ii = (unsigned char*)in + in_len - t;
	if (op == (unsigned char*)out && t <= 238)
	    *op++ = (unsigned char) ( 17 + t );
	else if (t <= 3)
	    op[-2] |= (unsigned char)t ;
	else if (t <= 18)
	    *op++ = (unsigned char)(t-3);
	else {
	    unsigned long tt = t - 18;

	    *op++ = 0;
	    while (tt > 255) {
			tt -= 255;
			*op++ = 0;
	    }
	    *op++ = (unsigned char)tt;
	}
	do *op++ = *ii++; while (--t > 0);
    }

    *op++ = 17;
    *op++ = 0;
    *op++ = 0;

    return (op - (unsigned char*)out);
}
